package leetcode.code0095;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution1 implements IDebug {

	public List<TreeNode> generateTrees(int n) {
		return this.f(1, n);
	}

	private List<TreeNode> f(int start, int end) {
		if (start > end) {
			return null;
		}
		List<TreeNode> ans = new ArrayList<>();
		for (int i = start; i <= end; i++) {
			List<TreeNode> lefts = this.f(start, i - 1);
			List<TreeNode> rights = this.f(i + 1, end);
			if (lefts == null && rights != null) {
				for (TreeNode right : rights) {
					TreeNode root = new TreeNode(i);
					root.right = right;
					ans.add(root);
				}
			} else if (lefts != null && rights == null) {
				for (TreeNode left : lefts) {
					TreeNode root = new TreeNode(i);
					root.left = left;
					ans.add(root);
				}
			} else if (lefts != null && rights != null) {
				for (TreeNode left : lefts) {
					for (TreeNode right : rights) {
						TreeNode root = new TreeNode(i);
						root.left = left;
						root.right = right;
						ans.add(root);
					}
				}
			} else {
				TreeNode root = new TreeNode(i);
				ans.add(root);
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<TreeNode> r = this.generateTrees(8);
//		List<TreeNode> e = TreeArray.array2tree(H.str2array4("[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]"));
//		H.compare(e, r);

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
